package _18_剑指OfferII;

import _18_剑指OfferII.datastrcute.TreeNode;

public class _054_剑指OfferII所有大于等于节点的值之和 {

    int n;
    // 逆中序遍历, 直接获取结果
    public TreeNode convertBST(TreeNode root) {
        if (root == null) return null;
        convertBST(root.right);
        root.val += n;
        n = root.val;
        convertBST(root.left);
        return root;
    }


    private int total;

    public TreeNode convertBST1(TreeNode root) {

        this.total = calTotal(root);
        dfs(root);
        return root;
    }

    private void dfs(TreeNode root) {
        if (root == null) return;;
        dfs(root.left);
        System.out.println(root.val);
        int temp = root.val;
        root.val = total;
        total -= temp;
        dfs(root.right);
    }

    private int calTotal(TreeNode root) {
        if (root == null) return 0;
        return root.val + calTotal(root.left) +  calTotal(root.right);
    }

}
